package com.lz.miniwindow;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Leetcode {

    public static void main(String[] args) {
        Leetcode leetcode = new Leetcode();
        String s1 = "";
        String s2 = "";
        String s = leetcode.minWindow("ADOBECODEBANC", "ABC");
//        System.out.println(s);
        List<Integer> integers = leetcode.minWindowYiWei("cbaebabacd", "abc");
//        System.out.println(integers);

        int bbb = leetcode.lengthOfLongestSubstring("abcabd");
        System.out.println(bbb);

    }

    /**
     * 76. 最小覆盖子串
     * <p>
     * 输入: S = "ADOBECODEBANC", T = "ABC"
     * 输出: "BANC"
     * <p>
     * 代码中 1+x，都不能替换++1
     *
     * @param s
     * @param t
     * @return
     */
    public String minWindow(String s, String t) {

        Map<Character, Integer> tMap = new HashMap<>();

        Map<Character, Integer> winMap = new HashMap<>();
        //  细节l0设置为最小值
        int l0 = Integer.MIN_VALUE, r0 = -1;

        int l = 0, r = 0;

        for (char m : t.toCharArray()) {
            Integer integer = tMap.getOrDefault(m, 0);
            tMap.put(m, 1 + integer);
        }
        // 这也是难点啊
        int matched = 0;

        while (r < s.length()) {

            char ch = s.charAt(r);

            Integer tCount = tMap.get(ch);

            if (tCount != null) {
                // 只统计t中包的字符串
                Integer windCount = winMap.getOrDefault(ch, 0);

                winMap.put(ch, 1 + windCount);

                if (tCount == 1 + windCount) matched++;
            }

            while (l <= r && matched == tMap.keySet().size()) {

                if ((r - l) < (r0 - l0)) {
                    l0 = l;
                    r0 = r;
                }

                char key = s.charAt(l);

                Integer tCount01 = tMap.get(key);

                Integer winCount = winMap.get(key);

                if (tCount01 != null) {
                    // 减了以后作比较
                    if (winCount <= tCount01) matched--;
                    winMap.put(key, winCount - 1);
                    // 这一步太关键了
                }
                l++;
            }
            r++;
        }
        // 判断没有字符串就尴尬
        if (r0 == -1) return "";

        return s.substring(l0, r0 + 1);
    }

    /**
     * ++ 形式真坑，手动拆箱 速度不及自动拆箱
     *
     * @param s
     * @param t
     * @return
     */
    public String minWindow02(String s, String t) {

        Map<Character, Integer> tMap = new HashMap<>();

        Map<Character, Integer> winMap = new HashMap<>();
        //  细节l0设置为最小值
        int l0 = Integer.MIN_VALUE, r0 = -1;

        int l = 0, r = 0;

        for (char m : t.toCharArray()) {
            Integer integer = tMap.getOrDefault(m, 0);
            tMap.put(m, ++integer);
        }
        // 这也是难点啊
        int matched = 0;

        while (r < s.length()) {

            char ch = s.charAt(r);

            Integer tCount = tMap.get(ch);

            if (tCount != null) {
                // 只统计t中包的字符串
                Integer windCount = winMap.getOrDefault(ch, 0);

                winMap.put(ch, ++windCount);
                // 没有自动拆箱的坑
                if (tCount.intValue() == windCount.intValue()) matched++;
            }

            while (l <= r && matched == tMap.keySet().size()) {

                if ((r - l) < (r0 - l0)) {
                    l0 = l;
                    r0 = r;
                }

                char key = s.charAt(l);

                Integer tCount01 = tMap.get(key);

                Integer winCount = winMap.get(key);

                if (tCount01 != null) {
                    // 减了以后作比较
                    winMap.put(key, --winCount);
                    if (winCount < tCount01) matched--;
                    // 这一步太关键了
                }
                l++;
            }
            r++;
        }
        // 判断没有字符串就尴尬
        if (r0 == -1) return "";

        return s.substring(l0, r0 + 1);
    }

    /**
     * 438.找到字符串中所有字母异位词
     *
     * @return
     */
    public List<Integer> minWindowYiWei(String s, String t) {
        // 用数组来代替
        int[] tCount = new int[256];
        int[] winCount = new int[256];
        List<Integer> list = new ArrayList<>();
        int k = 0;

        for (char ch : t.toCharArray()) {
            if (tCount[ch] == 0) k++;
            tCount[ch]++;
        }

        int matched = 0;
        int l = 0, r = 0;

        while (r < s.length()) {
            char c = s.charAt(r);
            int i = tCount[c];
            if (i != 0) {
                winCount[c]++;
                if (winCount[c] == i)
                    matched++;
            }

            while (l <= r && matched == k) {

                if (r - l == t.length() - 1) {
                    list.add(l);
                }

                char c1 = s.charAt(l);
                int i1 = tCount[c1];
                if (i1 != 0) {
                    winCount[c1]--;
                    if (i1 > winCount[c1]) matched--;
                }
                l++;
            }
            r++;
        }
        return list;
    }

    /**
     * 三、无重复字符的最长子串
     *
     * @param s
     * @return
     */
    int lengthOfLongestSubstring(String s) {

//        int[] tCount = new int[256];
        int[] winCount = new int[256];

        int max = 0;
        int l = 0, r = 0;

        while (r < s.length()) {

            char i = s.charAt(r);

            winCount[i]++;
            // 判断条件在外面
            if (winCount[i] <= 1) {
                int temp = r - l + 1;
                max = max > temp ? max : temp;
            }

            while (l <= r && winCount[i] > 1) {

                char cl = s.charAt(l);

                winCount[cl]--;
//                if (winCount[i] <= 1) {
//                    int temp = r - l + 1;
//                    max = max > temp ? max : temp;
//                }

                l++;
            }
            r++;
        }
        return max;
    }
}
